The present invention relates to a method for fingerprint information extraction by border line analysis of ridges and valleys of the print, the determination of average centerlines of the ridges and valleys, and the identification of minutiae of the ridges and valleys by their locations coupled with the average slope of the centerline at such minutiae.
Fingerprints have evolved as a standard for the positive identification of individual persons. They were first applied in the area of criminal investigation but, more recently, have also been applied to access control systems. Fingerprint identification in the law enforcement over many decades has demonstrated the uniqueness of the fingerprints of individuals. While it is theoretically possible that two fingerprints could be the same, such an occurrence has never been reliably documented. Barring an injury which causes scarring, a fingerprint pattern does not change with age. The ridge skin is live tissue that can change from day to day due to wear, and the ridge pattern will re-emerge, even after considerable abrasion.
Fingerprints are formed by raised friction ridges which aid in gripping objects and recessed valleys which separate the ridges. Fingerprint "minutiae" are conventionally defined as ridge endings or ridge bifurcations where a ridge splits into two ridges. Other fingerprint features or patterns, which can be visually recognized, are whorls which are concentric or spiral appearing patterns and deltas where a number of roughly parallel ridges appear to converge or diverge.
Early techniques for fingerprint classification and identification involved the analysis of the spatial relationships of major features and patterns which are visible to the human eye, often with the aid of optical magnification. Such visual techniques can be extremely laborious. In order to expedite the process, computerized fingerprint analysis techniques have been developed and refined.
Automated fingerprint analysis systems generally require that a "live" fingerprint or an ink replica of a fingerprint be optically scanned to digitally record the patterns of ridges and valleys as an ordered set of pixels or picture elements within a fingerprint data array. Each pixel has a binary value corresponding to its recorded color and a position within the array related to Cartesian coordinates of the pixel within the original image. Thus, the image can be reconstructed for visual display and the pixels can be addressed for analysis of the patterns thereof. Many fingerprint scanners record the fingerprint image in black and white, with logic zeros representing valley pixels as black and logic ones representing ridge pixels as white, although the designation of valleys and ridges respectively as logic zeros and ones or black and white, or any other colors, is arbitrary.
The great majority of conventional automated fingerprint analysis systems employ a "thinning" process on the image array to skeletonize the represented image to facilitate the techniques used to detect and locate features which are machine recognizable, such as line endings and bifurcations, referred to as minutiae, and the slope of the ridges near the detected minutiae. In general, thinning is a multiple pass process which progressively shaves away excess pixels of the ridges, for example, until the ridge is reduced to a single line of pixels having a shape approximating that of the original ridge.
A significant problem with thinning in fingerprint analysis is that thinning introduces errors. Thinning not only strips away pixels along the sides of ridges, but from the ends as well. Thus, line endings are displaced from their actual positions. Another problem with thinning is the creation of "false minutiae". Particles of dust, flaked skin, oils, and other extraneous matter can lodge within the valleys between the ridges of a fingerprint. Additionally, an optical scan of a fingerprint, at the resolution commonly used, can detect skin pores which can occur along a ridge. The thinning process often results in a bridge between ridges caused by extraneous matter and in ridge gaps where pores occur. The bridges are analyzed as false bifurcations, and the pores are analyzed as either as false bifurcations or false line endings. Such false minutiae not only reduce the accuracy of the data representing a particular fingerprint but also increase the quantity of data within such a data file. Another problem with analysis of thinned fingerprint images is that thinning the ridges makes it impossible to accurately analyze the original valleys which, being complementary to the ridges, can provide additional identification data of the fingerprint or at least data to corroborate the accuracy of the data derived from the ridges.
The pixels of a fingerprint array in which the ridges have been skeletonized by thinning may be analyzed using a "roving box" technique in which the color of each orthogonally and diagonally adjacent pixel to each pixel is tested. Such analysis is used to detect the minutiae of the ridges of the fingerprint. Process time is conserved to some extent by not checking pixels adjacent a background pixel. However, at bifurcations of lines, redundant indications of bifurcation occur. Additionally, any line consisting of at least two pixels results in two line ending entries in the minutia table related to the fingerprint. The result of such analysis of a thinned fingerprint image is a minutia table having a large number of entries, many of which are of minimal significance. The time required for comparing the minutia tables of fingerprints analyzed in this manner is considerable because of the large number of entries in the minutia tables.
While automated fingerprint analysis has been employed in investigative areas to identify unknown persons, there is a growing interest in using fingerprints to verify the identity of an individual, as for access control systems. One of the practical requirements of an access control system, especially as related to entry through security doors, is that the verification occur quickly. Verification of identity using fingerprints can be expedited by an enrollment process in which a database is constructed from a minutia table of a fingerprint of each individual having access rights or privileges, in combination with means such as a personal identification number or PIN.
Entry of the PIN quickly accesses the corresponding minutia table. A live fingerprint scan is taken, the digitized fingerprint is analyzed, and the live minutia table is compared with the enrolled minutia table. No two fingerprint scans of a given finger are exactly identical. Factors such as the force of pressing the finger tip on the scanner window and even instantaneous blood pressure can cause minor differences between scans taken in immediate succession. Therefore, a scoring system is generally used to judge the comparison of one minutia table with another. A threshold number of comparison "hits" or matches of minutiae is required to trigger a verification signal which releases a security door or the like.
In thinned image fingerprint verification systems, the time required to thin the image, detect minutiae, and compare minutia tables can amount to a number of seconds and even several minutes in some cases, even with a relatively fast computer which processes the information. Such a length of verification time would be impractical, for example, at a research and development facility, an industrial plant, or the like having a large number of workers who must routinely pass through numerous security doors to move throughout the plant.
In order to make fingerprint based access control systems practical, a method of fingerprint analysis is needed which is much faster and more accurate than conventional systems based on roving box analysis of thinned fingerprint images.